import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。
 *
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 *
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 */
public class Test120 {
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));
        System.out.println(minimumTotal(triangle));
    }

    public static int minimumTotal(List<List<Integer>> triangle) {
        List<List<Integer>> path = new ArrayList<>();
        path.add(triangle.get(0));
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j == 0){
                    int top = path.get(i-1).get(j);
                    list.add(top+triangle.get(i).get(j));
                }else if(j == triangle.get(i).size()-1){
                    int left_top = path.get(i-1).get(j-1);
                    list.add(left_top+triangle.get(i).get(j));
                }else{
                    int top = path.get(i-1).get(j);
                    int left_top = path.get(i-1).get(j-1);
                    list.add(Math.min(top,left_top)+triangle.get(i).get(j));
                }
            }
            path.add(list);
        }

        int min = path.get(path.size()-1).get(0);
        for (int i = 1; i < path.get(path.size()-1).size(); i++) {
            if (path.get(path.size()-1).get(i) < min){
                min = path.get(path.size()-1).get(i);
            }
        }
        return min;
    }
}
